﻿#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
//求⼀个整数存储在内存中的⼆进制中1的个数
//int main()
//{    
//	int n;
//	scanf("%d", &n);
//	int i = 0; int tem = 1;
//	int count = 0;
//	for (i = 0; i < 32; i++)
//	{
//		if ((n & tem) == 1)
//			count++;
//		n = n >> (i+1);
//	}
//	printf("%d\n", count);
//	return 0;
//}
//////编写代码将13⼆进制序列的第5位修改为1，然后再改回0?
//int main()
//{   
//	int n = 13;
//	int tem = 16;
//	n = n | tem;
//	printf("%d\n", n);
//	n = n & 13;
//	printf("%d\n", n);
//	return 0;
//}
//int main()
//{   
//	int n = 13;
//	n = n | (1 << 4);
//	printf("%d\n", n);
//	n = n & ~(1 << 4);
//	printf("%d\n", n);
//	return 0;
//}
//两个int（32位）整数m和n的二进制表达中，有多少个位(bit)不同？ 
//int main()
//{
//	int m, n;
//	scanf("%d %d", &m, &n);
//	int i = 0; int count = 0;
//	int tem = m ^ n;
//	for (i = 0; i < 32; i++)
//	{
//		if ((tem & (1 << i)) != 0)
//			count++;
//	}
//	printf("%d\n", count);
//	return 0;
//}
////////获取一个整数二进制序列中所有的偶数位和奇数位，分别打印出二进制序列
//void print(int n)
//{
//	int i = 0;
//	for (i = 31; i>=0; i--)
//	{
//		printf("%d",(n>>i)&1);
//	}
//	printf("\n");
//	for (i = 31; i >= 0; i -= 2)
//	{
//		printf("%d", (n >> i) & 1);
//	}
//	printf("\n");
//
//	for (i = 30; i >= 0; i -= 2)
//	{
//		printf("%d", (n >> i) & 1);
//	}
//	printf("\n");
//
//}
//int main()
//{   
//	int n;
//	scanf("%d", &n);
//	print(n);
//	return 0;
//}
//写一个函数返回参数二进制中 1 的个数。
//int judge(int n)
//{
//	int count = 0;
//	int i = 0;
//	for (i = 0; i < 32; i++)
//	{
//		if ((n & (1 << i)) != 0)
//			count++;
//	}
//	return count;
//}
//int main()
//{  
//	int n;
//	scanf("%d", &n);
//	int ret=judge(n);
//	printf("%d\n", ret);
//	return 0;
//}
///////不允许创建临时变量，交换两个整数的内容
//int main()
//{   
//	int a, b;
//	scanf("%d %d", &a, &b);
//	a = a ^ b;
//	b = a ^ b;
//	a = a ^ b;
//	printf("%d ", a);
//	printf("%d ", b);
//	return 0;
//}
////////使用指针打印数组内容
//int main()
//{  
//	int arr[10] = { 1,2,3,4,5,6,7,8,9,10 };
//	int* pa = arr;
//	for (int i = 0; i < 10; i++)
//	{
//		printf("%d ", pa[i]);
//	}
//	return 0;
//}
////////写一个函数，可以逆序一个字符串的内容。
//#include<string.h>
//void change(char* arr,int len)
//{
//	int left = 0; int right = len - 1;
//	char tem = 0;
//	while (left < right)
//	{
//		tem = arr[left];
//		arr[left] = arr[right];
//		arr[right] = tem;
//		left++; right --;
//	}
//
//}
//int main()
//{  
//	char arr[200];
//	fgets(arr, sizeof(arr), stdin);
//	int len = strlen(arr);
//	change(arr,len);
//	printf("%s\n", arr);
//	return 0;
//}
//////////求Sn=a+aa+aaa+aaaa+aaaaa的前5项之和，其中a是一个数字，
//例如：2 + 22 + 222 + 2222 + 22222
//int main()
//{  
//	int a;
//	scanf("%d", &a);
//	int sum = 0; int tem = a; int i = 0;
//	for (i = 0; i < 5; i++)
//	{
//		sum += tem;
//		tem = tem * 10 + a;
//	}
//	printf("%d\n", sum);
//	return 0;
//}
                                                     //////打印菱形
//#define Lhigh (line-1)/2+1
//#define Llow (line-1)/2
//int main()
//{
//	int line = 0;
//	while(scanf("%d",&line)!=EOF)
//	{
//		int i = 0;
//		for (i = 0; i < Lhigh; i++) //打印上半部分;
//		{
//			int j = 0;
//			for (j = 0; j < line - 1 - 2 * i; j++)  //打印空格； 
//			{
//				printf(" ");
//			}
//			for (j = 0; j < 2 * (i + 1) - 1; j++)//打印*
//			{
//				printf("* ");
//			}
//			printf("\n");
//		}
//		for (i = 0; i < Llow; i++)   //打印下半部分;
//		{
//			int j = 0;
//			for (j = 0; j < 2 + 2 * i; j++)  //打印空格;
//			{
//				printf(" ");
//			}
//			for (j = 0; j < line - 2 * (i + 1); j++)  //打印*;
//			{
//				printf("* ");
//			}
//			printf("\n");
//		}
//	}
//	return 0;
//}
///////递归方式实现打印一个整数的每一位
//void print(int n)
//{
//    if (n > 9)
//    {
//        print(n / 10);
//    }
//    printf("%d ", n% 10);
//}
//int main()
//{   
//    int n;
//    scanf("%d", &n);
//    print(n);
//    return 0;
//}
///////////递归和非递归分别实现求n的阶乘（不考虑溢出的问题）
//int main()
//{  
//    int n; int sum = 1;
//    scanf("%d", &n);
//    for (int i = 1; i <= n; i++)
//    {
//        sum *= i;
//    }
//    printf("%d\n", sum);
//    return 0;
//}
//int Fun(int n)
//{
//    if (n == 1)
//        return 1;
//    else
//        return Fun(n - 1) * n;
//}
//int main()
//{
//    int n;
//    scanf("%d", &n);
//    int ret=Fun(n);
//    printf("%d\n", ret);
//    return 0;
//}
//////////递归和非递归分别实现strlen
//int my_strlen(char* pa)
//{
//    if (*pa != '\0')
//    {
//        pa++;
//        return my_strlen(pa) + 1;
//    }
//    else
//        return 0;
//}
//int main()
//{   
//    char arr[500];
//    scanf("%s", arr);
//    int ret = my_strlen(arr);
//    printf("%d\n", ret);
//    return 0;
//}
////////写一个递归函数DigitSum(n)，输入一个非负整数，返回组成它的数字之和
//int DigitSum(int n)
//{
//    if (n > 9)
//    {
//        return DigitSum(n / 10)+n%10;
//    }
//    else
//        return n;
//
//}
//#include<assert.h>
//int main()
//{   
//    int n;
//    scanf("%d", &n);
//    assert(n >= 0);
//    int ret = DigitSum(n);
//    printf("%d\n", ret);
//    return 0;
//}
/////递归实现n的k次方
//int my_pow(int n, int k)
//{
//    if (k > 0)
//        return my_pow(n, k - 1) * n;
//    else
//        return 1;
//}
//int main()
//{ 
//    int n, k;
//    scanf("%d %d", &n,&k);
//    int ret = my_pow(n, k);
//    printf("%d\n", ret);
//    return 0;
//}
////////////递归和非递归分别实现求第n个斐波那契数
//int Fib(int n)
//{
//    int a = 1; int b = 1; int c = 0;
//    if (n <= 2)
//        return 1;
//    else
//    {
//        while (n - 2)
//        {
//            c = a;
//            a = b;
//            b = b + c;
//            n--;
//        }
//        return b;
//    }
//}
//int main()
//{ 
//    int n;
//    scanf("%d", &n);
//    int ret=Fib(n);
//    printf("%d\n", ret);
//    return 0;
//}
/////////二分查找
//int search(int* arr,int sz,int tar)
//{
//    int left = 0; int right = sz - 1;
//    int mid = (left + right) / 2;
//    while (left <= right)
//    {
//        if (arr[mid] > tar)
//        {
//            right = --mid;
//            mid = (left + right) / 2;
//        }
//        else if (arr[mid] < tar)
//        {
//            left = ++mid;
//            mid = (left + right) / 2;
//        }
//        else
//        {
//            printf("找到了，下标为%d\n", mid);
//            return 0;
//        }
//    }
//    printf("找不到\n");
//    return 0;
//}
//int main()
//{ 
//    int arr[10] = { 1,2,3,4,5,6,7,8,9,10 };
//    int sz = sizeof(arr) / sizeof(arr[0]);
//    int target = 0;
//    scanf("%d", &target);
//    search(arr, sz, target);
//    return 0;
//}